"""
快速排序：
    概述：
        快速排序是一种基于分治法的排序算法，它的工作原理是：
        1. 选择一个基准元素，通常选择第一个元素或最后一个元素。
        2. 重新排序数组，将所有比基准元素小的元素放在基准元素的前面，所有比基准元素大的元素放在基准元素的后面。
        3. 递归地对基准元素前后的子数组进行排序。
    推理过程：
        1. 选择第一个元素作为基准元素。
        2. 从数组的最后一个元素开始，从后往前遍历，找到第一个比基准元素小的元素，交换位置。
        3. 从数组的第一个元素开始，从前往后遍历，找到第一个比基准元素大的元素，交换位置。
        4. 重复第二步和第三步，直到遍历完数组。
        5. 递归地对基准元素前后的子数组进行排序。
    时间复杂度：
        快速排序的时间复杂度是：
            最好情况：O(nlogn)：每次划分都能将数组一分为二，时间复杂度为O(logn)，每次比较的次数为n，所以时间复杂度为O(nlogn)。
            最坏情况：O(n^2)：每次划分都不能将数组一分为二，时间复杂度为O(n)，每次比较的次数为n，所以时间复杂度为O(n^2)。
            平均情况：O(nlogn)
    空间复杂度：
        快速排序的空间复杂度是O(logn)。
    稳定性：不稳定
"""
# 1: 定义函数，quick_sort(my_list, left, right)
# 将数据一分为二，根据基准值一分为二
# start：左边界 end：右边界
# start: 开始下标，end：结束下标，第一次执行的时候start：下标0 end：下标4
def quick_sort(my_list, start, end, depth=0):
    indent = "│   " * depth  # 缩进表示递归深度
    print(f"{indent}┌─ 进入快排: start={start}, end={end}, 当前列表: {my_list}")

    # 1.1: 递归结束条件
    # TODO 递归终止条件：当子序列只剩一个元素或为空时（start >= end）
    if start >= end:
        print(f"{indent}└─ 递归终止 (start={start} >= end={end})")
        return

    # 1.2: 定义变量left和right，分别表示：起始索引和结束索引
    # TODO 初始化左右指针，左指针指向子序列开头，右指针指向子序列末尾
    left = start
    right = end
    print(f"{indent}│ 初始化: left={left}, right={right}")

    # 1.3: 获取基准值（middle），表示分界值，假设列表的第一个元素为基准值
    # TODO 选择基准元素（这里取子序列的第一个元素作为基准）
    middle = my_list[left]
    print(f"{indent}│ 选取基准值: middle={middle} (位置={left})")
    print(f"{indent}│ 分区开始: {my_list}")

    # 1.4：具体的排序过程，只要left<right,就说明没有找完（右边还有值），需要一直找
    # TODO 分区操作：将比基准小的元素移到左侧，比基准大的元素移到右侧
    while left < right:
        # 1.5: 把分界值右边比分界值小的元素，放到分界值左边
        # 1.5.1: 如果right索引的元素，比分界值大,则,right索引向左移动一位
        # TODO 从右向左找第一个小于基准的元素
        print(f"{indent}│ > [右扫] 位置 {right}: {my_list[right]}", end="")
        while my_list[right] >=middle and left < right:
            print(f" >= {middle}, 继续左移", end="")
            right -= 1
            if left < right:  # 避免越界访问
                print(f" → {right}: {my_list[right]}", end="")
        print()
        # 1.5.2：走到这里，说明right索引的元素，比分界值小，则交换两个元素的位置
        # TODO 将找到的小元素移到左侧空位
        my_list[left] = my_list[right]
        print(f"{indent}│   移动右侧小数到左坑: {my_list} (位置 {right}→{left})")

        # 1.6: 把分界值左边比分界值大的元素，放到分界值右边
        # 1.6.1 如果left索引的元素，比分界值小，则，left索引向右移动一位
        # TODO 从左向右找第一个大于等于基准的元素
        print(f"{indent}│ > [左扫] 位置 {left}: {my_list[left]}", end="")
        while my_list[left] < middle and left < right:
            print(f" < {middle}, 继续右移", end="")
            left += 1
            if left < right:  # 避免越界访问
                print(f" → {left}: {my_list[left]}", end="")
        print()

        # 1.6.2：走到这里，说明left索引的元素，比分界值大，则交换两个元素的位置
        # TODO 将找到的大元素移到右侧空位
        my_list[right] = my_list[left]
        print(f"{indent}│   移动左侧大数到右坑: {my_list} (位置 {left}→{right})")

    # 1.7: 走到这里，说明left>=right，即：left索引的位置，就是分界值的位置
    # TODO 将基准元素放入最终正确位置（此时left和right相遇）
    my_list[left] = middle
    pivot_pos = left  # 基准最终位置
    print(f"{indent}│ 基准归位: {my_list} (基准{middle}在位置{pivot_pos})")
    print(f"{indent}│ 分区结束: 左侧({start}-{pivot_pos - 1}), 右侧({pivot_pos + 1}-{end})")

    # 1.8:走到这里，说明本轮分界值位置已经被锁定，递归向下继续，分别对分界值左右两边重复操作即可
    # 1.8.1：分界值左边的数据，继续排序
    # TODO 递归排序基准左侧的子序列（所有小于基准的元素）
    print(f"{indent}│ 递归左侧: [{start}-{pivot_pos - 1}]")
    quick_sort(my_list, start, pivot_pos - 1, depth + 1)

    # 1.8.2：分界值右边的数据，继续排序
    # TODO 递归排序基准右侧的子序列（所有大于等于基准的元素）
    print(f"{indent}│ 递归右侧: [{pivot_pos + 1}-{end}]")
    quick_sort(my_list, pivot_pos + 1, end, depth + 1)

    print(f"{indent}└─ 返回列表: {my_list}")
if __name__ == '__main__':
    my_list = [5, 4, 1, 8, 3] # 相当于：[3, 4, 1, 5, 8]
    print("排序前：", my_list)
    quick_sort(my_list, 0, len(my_list) - 1)
    print("排序后：", my_list)
